/**************************************************
 * File: BST.h                                    *
 *                                                *
 *                                                *
 **************************************************/

#ifndef BST_H
#define BST_H

//BSTNode Struct
template <typename Object>
struct BSTNode
{
	Object Data;
	BSTNode* Left;
	BSTNode* Right;

	BSTNode (void)
	{
		Left = NULL;
		Right = NULL;
	}
	BSTNode (const Object & data, BSTNode* left, BSTNode* right)
	{
		Data = data;
		Left = left;
		Right = right;
	}
};

namespace ADT
{
	namespace Trees
	{
		//Binary Search Tree
		template <typename Object>
		class BST
		{
			public:
				//Constructor(s)
				BST (void);
				BST (const BST & Copy);
				//Destructor
				~BST (void);

				//Public Methods
				const Object & FindMin (void) const;
				const Object & FindMax (void) const;
				bool Contains (const Object & X) const;
				bool IsEmpty (void) const;
				int GetNumberOfNodes (void) const;

				void MakeEmpty (void);
				void Insert (const Object & X);
				void Remove (const Object & X);

				const BST & operator = (const BST & Copy);

			private:
				//Private Methods
				BSTNode<Object>* _findMin (BSTNode<Object>* T) const;
				BSTNode<Object>* _findMax (BSTNode<Object>* T) const;
				bool _contains (const Object & X, BSTNode<Object>* T) const;
				void _makeEmpty (BSTNode<Object>* & T);
				void _insert (const Object & X, BSTNode<Object>* & T);
				void _remove (const Object & X, BSTNode<Object>* & T);
				BSTNode<Object>* _clone (BSTNode<Object>* T) const;

				//Private Members
				BSTNode<Object>* Root;
				unsigned int NumBSTNodes;
		};

		///////////////////////////
		// BST Class Definitions //
		///////////////////////////

		//Public Methods

		//Constructor(s)
		template <typename Object>
		BST<Object>::BST (void)
		{
			this->Root = NULL;
			this->NumBSTNodes = 0;
		}

		template <typename Object>
		BST<Object>::BST (const BST & Copy)
		{
			this = Copy;
		}

		//Destructor
		template <typename Object>
		BST<Object>::~BST (void)
		{
			this->MakeEmpty();
		}

		//Public Methods
		template <typename Object>
		const Object & BST<Object>::FindMin (void) const
		{
			return this->_findMin(Root)->Data;
		}

		template <typename Object>
		const Object & BST<Object>::FindMax (void) const
		{
			return this->_findMax(Root)->Data;
		}

		template <typename Object>
		bool BST<Object>::Contains (const Object & X) const
		{
			return this->_contains(X, Root);
		}

		template <typename Object>
		bool BST<Object>::IsEmpty (void) const
		{
			if (Root == NULL)
				return true;
			else
				return false;
		}

		template <typename Object>
		int BST<Object>::GetNumberOfNodes (void) const
		{
			return this->NumBSTNodes;
		}

		template <typename Object>
		void BST<Object>::MakeEmpty (void)
		{
			this->_makeEmpty(Root);
		}

		template <typename Object>
		void BST<Object>::Insert (const Object & X)
		{
			this->_insert(X, Root);
		}

		template <typename Object>
		void BST<Object>::Remove (const Object & X)
		{
			this->_remove(X, Root);
		}

		template <typename Object>
		const BST<Object> & BST<Object>::operator = (const BST & Copy)
		{
			if (this != &Copy)
			{
				this->MakeEmpty();
				Root = _clone(Copy.Root);
			}
			return *this;
		}

		//Private Methods

		template <typename Object>
		BSTNode<Object>* BST<Object>::_findMin (BSTNode<Object>* T) const
		{
			if (T == NULL)
				return NULL;
			else if (T->Left == NULL)
				return T;
			else
				return this->_findMin(T->Left);
		}

		template <typename Object>
		BSTNode<Object>* BST<Object>::_findMax (BSTNode<Object>* T) const
		{
			if (T == NULL)
				return NULL;
			else if (T->Right == NULL)
				return T;
			else
				return this->_findMax(T->Right);
		}

		template <typename Object>
		bool BST<Object>::_contains (const Object & X, BSTNode<Object>* T) const
		{
			if (T == NULL)
				return false;
			else if (X < T->Data)
				return this->_contains(X, T->Left);
			else if (X > T->Data)
				return this->_contains(X, T->Right);
			else
				return true;
		}

		template <typename Object>
		void BST<Object>::_makeEmpty (BSTNode<Object>* & T)
		{
			if (T != NULL)
			{
				this->_makeEmpty(T->Left);
				this->_makeEmpty(T->Right);
				delete T;
			}
			T = NULL;
			this->NumBSTNodes = 0;
		}

		template <typename Object>
		void BST<Object>::_insert (const Object & X, BSTNode<Object>* & T)
		{
			if (T == NULL)
			{
				T = new BSTNode<Object>(X, NULL, NULL);
				this->NumBSTNodes++;
			}
			else if (X < T->Data)
				this->_insert(X, T->Left);
			else if (X > T->Data)
				this->_insert(X, T->Right);
		}

		template <typename Object>
		void BST<Object>::_remove (const Object & X, BSTNode<Object>* & T)
		{
			if (T != NULL)
			{
				if (X < T->Data)
					this->_remove(X, T->Left);
				else if (X > T->Data)
					this->_remove(X, T->Right);
				else if ((T->Left != NULL) && (T->Right != NULL))
				{
					T->Data = this->_findMin(T->Right)->Data;
					this->_remove(T->Data, T->Right);
				}
				else
				{
					BSTNode<Object>* oldBSTNode = T;
					if (T->Left != NULL)
						T = T->Left;
					else
						T = T->Right;
					delete oldBSTNode;
					this->NumBSTNodes--;
				}
			}
		}

		template <typename Object>
		BSTNode<Object>* BST<Object>::_clone (BSTNode<Object>* T) const
		{
			if (T == NULL)
				return NULL;
			else
				return new BSTNode<Object>(T->Data, this->_clone(T->Left), this->_clone(T->Right));
		}
	}
}

#endif